class Solution:
	# @param height, a list of integer
	# @return an integer
	def __init__(self):
		self.height = None

	def largestRectangleArea(self, height):
		self.height = height

		if len(height) == 0:
			return 0
		if len(height) == 1:
			return height[0]
		return self.maxArea(0, len(height)-1)

	def maxArea(self, start, end):
		if start == end:
			return self.height[start]

		mid = (start + end) / 2
		# max value from left
		ans = self.maxArea(start, mid)
		# max value from right
		ans = max(ans, self.maxArea(mid+1, end))
		# max value expanded from mid
		ans = max(ans, self.maxAreaFromMid(start, mid, end))

		return ans

	def maxAreaFromMid(self, start, mid, end):
		i, j = mid, mid+1
		ans = 0
		h = self.height[mid]
		while i >= start and j <= end:
			h = min(h, self.height[i], self.height[j])
			ans = max(ans, h*(j-i+1))
			if i == start:
				j += 1
			elif j == end:
				i -= 1
			else:
				if self.height[i-1] >= self.height[j+1]:
					i -= 1
				else:
					j += 1
		return ans

if __name__ == '__main__':
	l = [4,2,0,3,2,4,3,4]
	so = Solution()
	ans = so.largestRectangleArea(l)
	print ans